/*
 * $Id: Array.hpp 59 2009-02-19 10:30:57Z hyunghwan.chung $
 *
   Copyright 2005-2009 Chung, Hyung-Hwan.

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an  BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
 */

#ifndef _XP_BAS_ARRAY_CLASS_
#define _XP_BAS_ARRAY_CLASS_

#include <xp/types.h>
#include <xp/macros.h>
#include <xp/bas/assert.h>

XP_BEGIN_NAMESPACE2 (xp, bas)

template <typename T>
class Array
{
public:
	enum 
	{
		DEFAULT_CAPACITY = 128,
		DEFAULT_GROW_FACTOR = 128,
		INVALID_INDEX = ~(xp_size_t)0
	};

	Array (
		xp_size_t buffer_size = DEFAULT_CAPACITY,
		xp_size_t grow_factor = DEFAULT_GROW_FACTOR)
	{
		if (grow_factor <= 0) grow_factor = 1;

		if (buffer_size <= 0) {
			this->data_buffer = XP_NULL;
			this->buffer_size = 0;
		}
		else {
			this->data_buffer = new T[buffer_size];
			this->buffer_size = buffer_size;
		}
		this->grow_factor = grow_factor;
		this->data_count  = 0;
	}

	Array (const Array<T>& array)
	{
		if (array.data_buffer == XP_NULL) {
			this->data_buffer = XP_NULL;
			this->buffer_size = 0;
			this->grow_factor = array.grow_factor;
			this->data_count  = 0;
		}
		else {
			T* tmp = XP_NULL;
			xp_assert (array.buffer_size > 0 && array.grow_factor > 0);

			try {  
				tmp = new T[array.buffer_size];
				for (xp_size_t i = 0; i < array.data_count; i++) {
					tmp[i] = array.data_buffer[i];
				}
			}
			catch (...) {
				// just in case where the assignment throws an 
				// exception. when T is a class type, the operator = 
				// for the class may throw an exception.
				if (tmp != XP_NULL) delete[] tmp;
				throw;
			}

			this->data_buffer = tmp;
			this->buffer_size = array.buffer_size;
			this->grow_factor = array.grow_factor;
			this->data_count  = array.data_count;	
		}
	}
	
	~Array ()
	{
		if (this->data_buffer) delete[] this->data_buffer;
	}

	Array<T>& operator= (const Array<T>& array)
	{
		if (this != &array)
		{
			this->setSize (array.data_count);
			for (xp_size_t i = 0; i < array.data_count; i++) {
				this->data_buffer[i] = array.data_buffer[i];
			}
		}
		return *this;
	}

	/*
	Array<T>& operator+= (const T& value)
	{
		addDatum (value);
		return *this;
	}
	Array<T>& operator+ (const T& value) const
	{
		Array<T> array (*this);
		array.addDatum (value);
		return array;
	}
	*/

	xp_size_t size () const
	{
		return this->data_count;
	}
	bool isEmpty () const
	{
		return this->data_count == 0;
	}
	xp_size_t capacity () const
	{
		return this->buffer_size;
	}
	xp_size_t growFactor () const
	{
		return this->grow_factor;
	}

	operator T* ()
	{
		return this->data_buffer;
	}

	operator const T* () const
	{
		return this->data_buffer;
	}

	T* buffer ()
	{
		return this->data_buffer;
	}

	const T* buffer () const
	{
		return this->data_buffer;
	}

	T& operator[] (xp_size_t index)
	{
		xp_assert (index < this->data_count);
		return this->data_buffer[index];
	}

	const T& operator[] (xp_size_t index) const
	{
		xp_assert (index < this->data_count);
		return this->data_buffer[index];
	}

	T& get (xp_size_t index)
	{
		xp_assert (index < this->data_count);
		return this->data_buffer[index];
	}

	const T& get (xp_size_t index) const
	{
		xp_assert (index < this->data_count);
		return this->data_buffer[index];
	}

	void set (xp_size_t index, const T& value)
	{
		xp_assert (index < this->data_count);
		this->data_buffer[index] = value;
	}

	xp_size_t getIndex (const T& v)
	{
		if (&v >= &this->data_buffer[0] && &v < &this->data_buffer[this->data_count])
		{
			return &v - &this->data_buffer[0];
		}

		return INVALID_INDEX;
	}
	
	xp_size_t insert (xp_size_t index, const T& value)
	{
		if (index >= this->buffer_size) 
		{
			if (index - this->buffer_size >= this->grow_factor)
				setCapacity (index + 1);
			else 
				setCapacity (this->buffer_size + this->grow_factor);
		}
		else if (this->data_count >= this->buffer_size) 
		{
			setCapacity (this->buffer_size + this->grow_factor);
		}

		for (xp_size_t i = this->data_count; i > index; i--) 
		{
			this->data_buffer[i] = this->data_buffer[i - 1];
		}
		this->data_buffer[index] = value;
		if (index > this->data_count) this->data_count = index + 1;
		else this->data_count++;

		return index;
	}
	
	void remove (xp_size_t index)
	{
		remove (index, index);
	}

	void remove (xp_size_t from_index, xp_size_t to_index)
	{
		xp_assert (from_index < this->data_count);
		xp_assert (to_index < this->data_count);

		xp_size_t j = from_index;
		xp_size_t i = to_index + 1;
		while (i < this->data_count) {
			this->data_buffer[j++] = this->data_buffer[i++];
		}
		this->data_count -= to_index - from_index + 1;
	}

	xp_size_t addDatum (const T& value)
	{
		return insert (this->data_count, value);
	}

	xp_size_t removeDatum (const T& value)
	{
		xp_size_t i = 0, sz = this->size();
		while (i < this->data_count) {
			if (value == this->data_buffer[i]) {
				remove (i);
				break;
			}
			i++;
		}

		return sz - this->size();
	}

	xp_size_t removeDatums (const T& value)
	{
		xp_size_t i = 0, sz = this->size();

		while (i < this->data_count) {
			if (value == this->data_buffer[i]) remove (i);
			else i++;
		}

		return sz - this->size();
	}

	void clear ()
	{
		setSize (0);
	}
	
	void trimToSize ()
	{
		setCapacity (this->size);
	}
	
	void setSize (xp_size_t size)
	{
		if (size > this->buffer_size) setCapacity (size);
		xp_assert (size <= this->buffer_size);
		this->data_count = size;
	}
	
	void setCapacity (xp_size_t buffer_size)
	{
		if (buffer_size <= 0) 
		{
			if (this->data_buffer != XP_NULL) 
				delete[] this->data_buffer;
			this->data_buffer = XP_NULL;
			this->buffer_size = 0;
			this->data_count  = 0;
		}
		else 
		{
			T* tmp = XP_NULL;
			xp_size_t cnt = this->data_count;

			try 
			{
				tmp = new T[buffer_size];
				if (cnt > buffer_size) cnt = buffer_size;
				for (xp_size_t i = 0; i < cnt; i++) 
				{
					tmp[i] = this->data_buffer[i];
				}
			}
			catch (...) 
			{
				if (tmp != XP_NULL) delete[] tmp;
				throw;
			}

			if (this->data_buffer != XP_NULL) 
				delete[] this->data_buffer;
			this->data_buffer = tmp;
			this->buffer_size = buffer_size;
			this->data_count = cnt;
		}
	}
	
	void setGrowFactor (xp_size_t grow_factor)
	{
		if (grow_factor <= 0) grow_factor = 1;
		this->grow_factor = grow_factor;
	}

	xp_size_t indexOf (const T& value) const
	{
		for (xp_size_t i = 0; i < this->data_count; i++) {
			if (this->data_buffer[i] == value) return i;
		}
		return INVALID_INDEX;
	}
	
	xp_size_t indexOf (const T& value, xp_size_t index) const
	{
		for (xp_size_t i = index; i < this->data_count; i++) {
			if (this->data_buffer[i] == value) return i;
		}
		return INVALID_INDEX;
	}
	
	xp_size_t lastIndexOf (const T& value) const
	{
		for (xp_size_t i = this->data_count; i > 0; ) {
			if (this->data_buffer[--i] == value) return i;
		}	
		return INVALID_INDEX;
	}
	
	xp_size_t lastIndexOf (const T& value, xp_size_t index) const
	{
		for (xp_size_t i = index + 1; i > 0; ) {
			if (this->data_buffer[--i] == value) return i;
		}
		return INVALID_INDEX;
	}
	
	void rotate (int dir, xp_size_t n)
	{
		xp_size_t first, last, count, index, nk;
		T c;

		if (dir == 0) return data_count;
		if ((n %= data_count) == 0) return data_count;

		if (dir > 0) n = data_count - n;
		first = 0; nk = data_count - n; count = 0; 

		while (count < n) {
			last = first + nk;
			index = first;
			c = this->data_buffer[first];
			while (1) {
				count++;
				while (index < nk) {
					this->data_buffer[index] = this->data_buffer[index + n];
					index += n;
				}
				if (index == last) break;
				this->data_buffer[index] = this->data_buffer[index - nk];
				index -= nk;
			}
			this->data_buffer[last] = c; first++;
		}
	}

protected:
	T* data_buffer;
	xp_size_t data_count;
	xp_size_t buffer_size;
	xp_size_t grow_factor;
};

XP_END_NAMESPACE2 (xp, bas)

#endif


